In recent years, as various types of information is generated and circulated, damage such as exposure of important information to a third party is caused due to hacking or transmission of information to an incorrect path.
In particular, when in the state where no defense mechanism is applied to the important information such as military information or personal information during a process of transferring information, the important information is accidentally transmitted to the third party, the third party can easily access the important information, thereby causing great damage.
In recent years, in order to prevent exposure of such important information, there has been introduced a technique of encrypting the important information by using a predetermined encryption key and transmitting the encrypted information to the other party.
In a general data encryption scheme, a scheme is used, in which when a data transmission side and a data reception side share the same secret key and the data transmission side encrypts the data with the secret key and transmits the encrypted data, the data reception side decrypts the data with the same secret key.
However, such a symmetric key based encryption scheme has a weak vulnerability in that there is a risk that the corresponding secret key is exposed in the process of transferring and sharing the secret key.
In order to solve the drawbacks of the symmetric key based encryption scheme, a data encryption method using an asymmetric key, which is called a public key and a private key, has been introduced. In the asymmetric key based data encryption scheme, a scheme is used, in which when the data transmission side encrypts data with the public key and transmits the encrypted data to the data reception side, the data reception side decrypts the data with the private key corresponding to the public key, or when the data transmission side encrypts the data with the private key and transmits the encrypted data to the data reception side, the data reception side decrypts the data with the public key.
Such an asymmetric key based data encryption scheme can minimize the risk of exposure of the encryption key because the data transmission side and the data reception side have different encryption keys.
In recent years, a McEliece encryption system has been introduced as a system to which such an asymmetric key based encryption scheme is applied. The McEliece encryption system is a system in which when a data transmission apparatus generates a public key Kpub by using a k×n (k and n is a natural number) sized generator matrix G having an error correction capability for a t (t is the natural number)-bit code, a k×k sized scrambling matrix S and an n×n sized permutation matrix P, encrypts a message m to be transmitted to a data reception apparatus with the public key Kpub and generates an encryption message c and thereafter, transmits the encryption message c to the data reception apparatus, the data reception apparatus decrypts the encryption message by using the generator matrix G, the scrambling matrix S, and the permutation matrix P prestored in a memory as the private key to restore the message m.
In this regard, a brief description of the data encryption and decryption schemes in the McEliece encryption system is as follows.
First, Kpub which is the public key used by the data transmission apparatus is defined by Equation 1 below.Kpub=SGP  [Equation 1]
Here, in Equation 1, the generator matrix G represents the k×n sized generator matrix having the error correction capability for the t-bit code, S represents a randomly determined k×k sized scrambling matrix, and P represents a randomly determined n×n sized permutation matrix.
In this case, the data reception apparatus stores each of the generator matrix G, the scrambling matrix S, and the permutation matrix P with the private key corresponding to the public key Kpub in the memory.
Under such a situation, the data transmission apparatus encodes the message m to be transmitted to the data reception apparatus into binary string data having a length of k and then performs an encryption operation on the encoded message m according to Equation 2 below to generate the encryption message c.c=mKpub⊕e  [Equation 2]
Here, e represents a random vector having a Hamming weight of t or less and having a length of n bits and “⊕” represents an exclusive OR operation.
The Hamming weight means the number of bit values of “1” in a bit string constituting data.
As such, when the encryption message c is generated, the data transmission apparatus completes the data encryption transmission by transmitting the encryption message c to the data reception apparatus.
When the encryption message c is transmitted from the data transmission apparatus to the data reception apparatus, the data reception apparatus uses the generator matrix G, the scrambling matrix S, and the permutation matrix P stored in the memory to decrypt the encryption message.
In this regard, when the encryption message c is received, the data reception apparatus calculates cP−1 by multiplying the encrypted message c by P−1, which is an inverse matrix of the permutation matrix P, as illustrated in Equation 3 below.cP−1=mSG⊕eP−1  [Equation 3]
Then, the data reception apparatus may calculate mS by performing data decoding for error correction using the generator matrix G from the cP−1.
Here, since the e represents the vector having the Hamming weight of t or less and P represents the permutation matrix, eP−1 also has the Hamming weight of t or less, and consequently, it can be seen that cP−1 represents that the error occurs with respect to t bit values or less in a codeword mSG. Therefore, the data reception apparatus performs the error correction on cP−1 using G, which is the generator matrix having the error correction capability for the t-bit code stored in the memory to decode mS.
When the calculation of the mS is completed, the data reception apparatus multiplies mS by S−1 which is the inverse matrix of the scrambling matrix S stored in the memory as illustrated in Equation 4 below to finally decode the original message m.mSS−1=m  [Equation 4]
In recent years, in the McEliece encryption system, the generator matrix of Reed-Muller (RM) codes is often used in connection with the generator matrix G. The RM code is a linear code used as an error correction code. The RM code expressed by RM(r, m) has a length of 2m and m basic codes, and a code having a multiplication of the m basic codes also may be a basic code of RM. r represents the maximum number of basic codes that can be used in the multiplication of the basic codes. For example, when m=4 and r=4, the length of the RM code is 16. In this case, since the RM code is represented by 24, the RM code has four basic codes R1, R2, R3, and R4 (the length of each basic code is 16). In this case, the RM code which calculates the multiplication of the four basic codes R1, R2, R3, and R4 can also be the basic code. Here, since r=4, the maximum number of codes usable for the multiplication of the four basic codes is four in order to generate other additional basic codes for four basic codes R1, R2, R3, and R4, and as a result, a maximum of four mutual multiplications of four basic codes R1, R2, R3, and R4 are combined and calculated to generate additional basic codes. In this regard, with respect to RM(4, 4), four basic codes corresponding to R1, R2, R3, R4 and 11 basic codes consisting of R1R2, R1R3, R1R4, R2R3, R2R4, R3R4, R1R2R3, R1R2R4, R1R3R4, R2R3R4, and R1R2R3R4 may be generated and since the RM code needs to have even a code having bit values of which all are configured by “1” as the basic code due to characteristics of the RM code, a total of 16 basic codes can be consequently generated. In this case, in the McEliece encryption system, the generator matrix G to be used when the message is encrypted by using a total of 16 basic codes can be generated.
Since the RM code has a high error correction capability, the RM code can be used usefully for enhancing security of the encryption system. However, since the RM code has a special structure, it is easy to guess the private key used for data decryption from the RM code. Therefore, if the RM code is just used in the McEliece encryption system, the risk of exposure of important data may increase.
In this regard, the related literature, ““Cryptanalysis of the Sidelnikov Cryptosystem”, Lorenz Minder et al., “Advances in cryptology—Eurocrypt 2007”, LNCS vol. 4515 (2007)” discloses an attack method for finding the permutation matrix P in the McEliece encryption system based on the characteristics of the RM code and ““The failure of McEliece PKC based on Reed-Muller codes.”, I. V. Chizhov et al., Prikl. Diskr. Mat. Suppl., 2013, Issue 6, Pages 48-49 (Oct. 9, 2013)” discloses a method for shorting the process in the attack method.
Therefore, it is necessary to study a method that can defend an attack of a hacker based on specificity of the RM code in the McEliece encryption system using the RM code.